package com.lw.leetcode.sort.b;

import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 1562. 查找大小为 M 的最新分组
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/26 10:17
 */
public class FindLatestStep {

    public static void main(String[] args) {
        FindLatestStep test = new FindLatestStep();
        // 4
        int[] arr = {3, 5, 1, 2, 4};
        int m = 1;

        // 2
//        int[] arr = {2, 1};
//        int m = 2;

        // 1
//        int[] arr = {1};
//        int m = 1;

        // -1
//        int[] arr = {3, 1, 5, 4, 2};
//        int m = 2;

        int latestStep = test.findLatestStep(arr, m);
        System.out.println(latestStep);
    }

    public int findLatestStep(int[] arr, int m) {
        int length = arr.length;
        if (m == length) {
            return length;
        }
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int sum = 0;
        int last = -1;
        for (int i = 0; i < length; i++) {
            int k = arr[i];
            Integer t = map.ceilingKey(k);
            Integer d = map.floorKey(k);
            int c = 1;
            int key = k;
            if (d != null) {
                int dc = map.get(d);
                if (d + dc == k) {
                    key = d;
                    c += dc;
                    if (dc == m) {
                        sum--;
                    }
                }
            }
            if (t != null) {
                int tc = map.get(t);
                if (t - 1 == k) {
                    c += tc;
                    map.remove(t);
                    if (tc == m) {
                        sum--;
                    }
                }
            }
            map.put(key, c);
            if (c == m) {
                sum++;
            }
            if (sum > 0) {
                last = i + 1;
            }
        }
        return last;
    }

}
